// 解题思路：
// 题目要求：找最长的俄罗斯套娃信封的长度
// 重写排序 + 贪心 + 二分：
// 首先将数组按照左端点进行排序，确保在第 i 位置信封的最大俄罗斯套娃信封长度的时候，只需要去左边找
// 左端点相同时，再将数组按照右端点降序排序，确保信封左端点相同的时候，遍历右边信封可以替代掉左边信封的高度
// 如果右边的信封高度大，宽度一定也大，一定需要新开一个位置
// 如果宽度大，高度小，也可以直接替代，因为后面信封能装这个信封，也一定也能装这个高度更小的信封

// 如果不降序排序，当右边信封的高度，小于左边信封高度的时候，就需要分类讨论：
// 如果右边宽度大于左边宽度，有可能需要替代这个信封，也有可能不需要替代（替代完宽度增大，有可能没法在后面再套信封）
// 如果右边宽度等于左边宽度，需要替代这个信封


import java.util.Arrays;

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> {
            if(a[0] != b[0]) return a[0] - b[0];
            else return b[1] - a[1];
        });

        int n = envelopes.length;
        int[] t = new int[n + 1];
        int pos = 0;

        for(int i = 0; i < n; i++){
            int w = envelopes[i][0]; int h = envelopes[i][1];

            if(pos == 0 || h > t[pos]){
                t[++pos] = h;
            }else{
                int left = 1; int right = pos; int mid = 0;
                while(left < right){
                    mid = (right - left) / 2 + left;
                    if(h > t[mid]){
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                if(h < t[left]){
                    t[left] = h;
                }
            }

        }

        return pos;
    }
}
